class Solution:
    def threeSumMulti(self, A: list, target: int) -> int:
        MOD = 10**9 + 7

        def two_sum(array, t):
            res = 0
            left = 0
            right = len(array) - 1
            while left < right:
                s = array[left] + array[right]
                if s < t:
                    left += 1
                elif s > t:
                    right -= 1
                elif array[left] != array[right]:
                    left_count = 1
                    right_count = 1
                    while left + 1 < right and array[left] == array[left + 1]:
                        left_count += 1
                        left += 1
                    while right - 1 > left and array[right] == array[right
                                                                     - 1]:
                        right_count += 1
                        right -= 1
                    res += (left_count * right_count)
                    left += 1
                    right -= 1
                else:
                    res += (right - left + 1) * (right - left) // 2
                    break
            return res

        A.sort()
        res = 0
        for i in range(len(A)):
            res += two_sum(A[i + 1:], target - A[i])
            res %= MOD
        return res
